perm filename OCCULT[00,BGB]2 blob sn#111641 filedate 1974-07-17 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	{[C <N αOCCULT λ30 P40 I425,0 JC FA}      SECTION 4.
C00005 00003	
C00009 00004	
C00010 00005	[4.1	Hide Marking a Coherent Object.]
C00014 00006	[4.2	Edge-Edge and Face-Vertex Comparing]
C00015 00007	[4.3	Recursive Windowing.]
C00019 00008	[4.4	Propagating Underfaces and Shadows.]
C00020 00009	[4.5	Photometric Modeling and Video Generation.]
C00022 00010	[4.6	Performance of OCCULT and Related Work.]
C00023 ENDMK
C⊗;
{[C; <N; αOCCULT; λ30; P40; I425,0; JC; FA}      SECTION 4.
{JC; FD}   HIDDEN LINE ELIMINATION FOR COMPUTER VISION.
{λ7; W250; JA; FA}
	4.0	Introduction to Hidden Line Elimination.
	4.1	Hide Marking a Coherent Object.
	4.2	Edge-Edge and Face-Vertex Comparing
	4.3	Recursive Windowing.
	4.4	Propagating Underfaces and Shadows.
	4.5	Photometric Modeling and Video Generation.
	4.6	Performance of OCCULT and Related Work.
	4.7	Summary of OCCULT Techniques.
{λ30;W0;I950,0;JUFA}
[4.0	Introduction to Hidden Line Elimination.]

	Hidden line elimination  refers to the process  of simulating
the  appearance  of  opaque  three  dimensional  objects. The  phrase
<hidden line elimination> dates  from when the problem only  involved
deleting the  undesired,  that  is the <hidden>  lines,  from  a line
drawing; today  the phrase persists but connotes the wider problem of
synthesizing  realistic  images  using  a  computer.     The  present
discussion  is about  techniques  which have  been  implemented in  a
particular hidden line  eliminator named OCCULT.   The name  <OCCULT>
literally means  <to hide>.   Employing the  GEOMED routines and  the
winged  edged  polyhedron  representation,  OCCULT illustrates  novel
solutions to the graphics problems of exploiting object coherence and
frame  coherence,     of  combining  image  space   and  model  space
techniques,   and of spatial sorting of  faces, edges and vertices in
two dimensions.

	OCCULT is further distingushed by its intended application to
computer  vision  and robotics.    Whereas in  computer  graphics the
results of hidden line elimination are intended for human viewing, in
computer  vision   the  output   is  intended  for   further  machine
processing.   In vision, the output of  a hidden line eliminator must
be in a form appropriate  for some kind of automatic  image comparing
process.   In particular,  the prime  design goal  for OCCULT  was to
output a coherent graph of  regions, edges and vertices that  covered
the  image  rectangle  plane with  no  holes  missing,    no  regions
overlapping and no dangling edges. It was naively assumed that such a
highly structured  image  representation, called  a  <mosaic  image>,
would provide a suitable basis for deriving data such as the location
and  orientation of  high contrast  edges without having  to generate
video image.

	The idea of using a hidden line eliminator in a vision system
is  not new and  has appeared  in two other  vision systems,   one by
Larry Roberts (ref  **) and one  by Gill Falk  (ref **); the  present
system is a direct heir of the  work of both Roberts and Falk in that
the  last  version of  the  Falk system  contained one  of  the early
versions of OCCULT (as installed by Richard Orban).

	Finally, I reject the  view that the hidden  line elimination
problem  has been  adequately solved.   Like  image anaylsis,   image
synthesis which is hidden line  elimination, is going to continue  to
be a perenial  research problem because  it can not be  isolated from
physical  modeling.  Metaphorically,  hidden line  elimination is the
visible tip of the iceberg of physical simulation,  weaknesses of the
underlying model literally shows up in passing through the process of
image synthesis.   The present day collection of techniques are still
quite lacking in realism, economy, flexibility and even reliability.


Initialization for Hidden Line Elimination.
---------------------------------------------------------------------
Perspective Projection

FMark
	Face Z-clipping
	Potent & Visible Bits
	Face Coefficients
EMark
	Edge Coefficients
	Folded Edges.
[4.1	Hide Marking a Coherent Object.]

	OCCULT marks  the faces, edges  and vertices of  a polyhedral
scene as being,  either visible or hidden with respect to a simulated
camera.  Edges that  were at first  partially visible are split  into
pieces so that each piece is either fully visible or fully hidden. In
a  modeling environment that provides coherent  polyhedra that can be
easily traveled and  modified, the simple  technique of hide  marking
the neighbors of entities already hidden can be used to do almost all
of the actual hiding, once a starting place has been found.

	In OCCULT,  the two  innermost routines,   EHIDE  and  VHIDE,
perform this kind of marking. The routine  VHIDE takes two arguments:
the vertex, V, which  is to be marked as hidden and the face, F, that
is known to  hide V;  the routine  then simply calls  EHIDE for  each
potentially visible edge of V's  perimeter. EHIDE in turn takes three
arguments:  an overface, F,  an edge, E,  and one vertex,  V, of that
edge which  is known  to be  hidden by F.  EHIDE then  checks to  see
whether or not E leaves its overface, F, there are three basic cases:
(i) E  does not  leave F,  so it  is marked  as hidden  and VHIDE  is
applied to  the vertex OTHER(E,V);  (ii) E does  leave overface  F by
crossing  under an edge  which provides a  new overface  for EHIDE to
check; or (iii)  E leaves F by  crossing under a  <folded> edge,   so
EHIDE splits  the original  edge, E,  and the folded  edge to  form a
T-joint  marking the hidden  portion of  E as hidden  and leaving the
remaining portion of E potentially visible.

T-joints & Folded Edges.

[4.2	Edge-Edge and Face-Vertex Comparing]

Edge-Edge Comparing

i.	Identity case (E1 ≡ E2)
ii.	Topologically connected
	  Test for edges already having a vertex of tjoint in common.
iii.	Span Overlap Test
	  to prevent nasty colinear cases.
iv.	Compare for crossing
v.	Fudge (Move towards right and down).

Face-Vertex Comparing

	Zdepth
	Within

	Two very simple kinds of hidden  line eliminators that almost
work  are  based  on  combining  edge-edge  comparing or  face-vertex
comparing with coherent object hidding.

[4.3	Recursive Windowing.]

	Recursive windowing is the 
will push them into a window and will then sub divide the
window recursively until a desired condition is achieved.

	This  section describes  a  two dimensional  spatial  sorting
technique for partitioning  the faces,  edges and vertices associated
with a given rectangular region called a window, into two subwindows.

The general idea of the sort technique
stems from the hidden line eliminators of Warnock (ref. **)
and  Sutherland  (ref. **);  however  ESORT  is  unique  in  that  it
maintains a data structure which  allows edges to be split during the
sort and its makes fewer compares than any of its predessors.

Window Structure.

	The sort window itself  is a twelve word node  which contains
data fields named XLO, XHI, YLO and YHI which specify the boundary of
the window and  data fields named  PENCNT, SURCNT,   EDGCNT and  VCNT
which  specify the  number of  faces that  penetrate or  surround the
window,   the number  of edges that  pass through the  window and the
number of vertices that  fall within the window. The  window contains
sufficient link fields  to hold pointers to the  head of the pen-face
list, the sur-face list,  the vertex list, the  head and tail of  its
edge list and a pointer to its antecedent window.

Bead Structure.

	A bead  is a two  word node that  contains four  pointers and
which  represents one instance of  an edge passing  through a window.
Each edge has  a list of  beads representing an  ordered list of  the
window through which it (the edge) passes; and each window has a list
of  beads representing  a  list of  the edges  it contains.  The link
fields named WND  and EDG of a  bead, point to the  particular window
and the  particular edge to which  the bead belongs.  The link fields
named WNBL and  EDBL of a  bead contain the  necessary links for  the
window's bead list and for the edge's bead list.

Routines:

	i.   Make Sort Window.
	ii.  Push Sort Window.
	iii. Pop Sort Window.
	iv.  Bead List Edit.
[4.4	Propagating Underfaces and Shadows.]

[4.5	Photometric Modeling and Video Generation.]

	The light scattering  properties of ordinary surfaces  can be
modeled  by  thinking  of the  surface  as  composed  of many  little
mirrors. The orientation of each  mirror is described by two  angles,
its tilt from the normal vector of  the surface and its pan about the
normal  vector with  respect to a  specified reference  vector in the
tangent plane of  the surface. For  a perfect reflecting surface  all
the  differential mirrors  have a  zero pan  and tilt;  for isotropic
conventional   surfaces   the   statistical   distribution   of   pan
orientations is flat and  the distribution of tilt orientations  is a
blip function; and  for a perfect isotropic Lambert surfaces both the
pan and tilt distributions are flat.

[4.6	Performance of OCCULT and Related Work.]

[4.7	Summary of OCCULT Techniques.]